#include <stdio.h>

/*
平均时间复杂度也是 O(n)
空间复杂度 O(1)
*/

// 函数用于顺序查找，返回目标元素的索引，或者-1表示未找到（不应该发生，因为有哨兵）
int sentinelSearch(int arr[], int n, int key) {
    int last = arr[n-1];  // 保存原数组最后一个元素的值
    arr[n-1] = key;       // 将哨兵设置为要查找的关键字

    int i = 0;
    // 继续遍历直到找到关键字
    while (arr[i] != key) {//最晚会在哨兵节点停止
        i++;
    }

    arr[n-1] = last;  // 恢复原数组最后一个元素的值

    if (i < n-1 || arr[n-1] == key) {
        return i;  // 如果在数组中找到关键字，或者关键字就在原数组的最后一个位置
    } else {
        return -1; // 如果哨兵位置的元素未被查找，说明原数组中没有关键字
    }
}

int main() {
    int data[] = {5, 3, 9, 2, 8, 10, 11};
    int size = sizeof(data) / sizeof(data[0]);
    int key = 10;

    int index = sentinelSearch(data, size, key);

    if (index != -1) {
        printf("Element found at index: %d\n", index);
    } else {
        printf("Element not found.\n");
    }

    return 0;
}
